// https://www.lintcode.com/problem/counting-universal-subarrays/

public class Solution {
    /**
     * @param array: An given array.
     * @return: Return the number of "universal" subarrays.
     */
    public int subarrays(int[] array) {
        // write your code here.
        /*
        只能出现[x, x, x, y, y, y]的形式
        思路：记录每个字符连续出多少次。
        - 如果x出现a次，y出现b次。
        - 可以生成min(a, b)个子序列。
        */
        int ret = 0;
        int prev = array[0];
        List<Integer> count = new ArrayList<>();
        count.add(1);
        for (int i = 1; i < array.length; ++i) {
            int c = array[i];
            if (c == prev) {
                count.set(count.size() - 1, count.get(count.size() - 1) + 1);
            } else {
                prev = c;
                count.add(1);
            }
        }
        for (int i = 1; i < count.size(); ++i) {
            ret += Math.min(count.get(i - 1), count.get(i));
        }
        return ret;
    }
}